题目大意
题目链接
很经典的问题。
n个人要过河， 过河需要保护罩， 一个保护罩最多只能容纳两个人， 每个人过去都有花费的时间， 如果两个人一起过，花费的总时间时间 就是两个人中 花费的时间最大的那个。
问怎么安排能尽快过河。
分析
十分经典的问题， 从小到大排序， 充分利用好a[1], a[2]， 一共有两种情况。
a[1], a[2] 过去， a[1]回来， a[i] 和 a[i - 1] 过去， a[2] 回来， 总花费是a[2] + a[1] + a[i] + a[2].
a[1]，a[i] 过去， a[1]回来， 总花费是a[1] + a[i]
然后用dp！！， dp[i] 表示前i (包括i)全都过河花费的最小时间。
dp[i] = min(dp[i - 2] + a[2] + a[1] + a[i] + a[2] ,dp[i - 1] + a[1] + a[i])
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
inline ll read() {
ll res = 0;bool f = 0;char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
return f ? (~res + 1) : res;
}
int a[100];
int f[100];
int main(){
int n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
sort(a + 1, a + n + 1);
f[1] = a[1], f[2] = a[2];
for (int i = 3; i <= n; ++i){
f[i] = min(f[i - 1] + a[1] + a[i], f[i - 2] + a[i] + 2 * a[2] + a[1]);
}
cout << f[n] << "\n";
return 0;
}
|
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。 --mingfuyan
千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。